
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    /**
     * 142环形链表Ⅱ
     * https://leetcode.cn/problems/linked-list-cycle-ii/
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        //思路：找出相遇点,然后slow从头走，fast从相遇点走，一人走一步，直到两节点相遇，就是入口处
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                //相遇了
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        } else {
            //fast回到head位置，slow和fast再同时走一步，相遇就是入口点
            fast = head;
            while(slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return fast;
    }

    /**
     * 876链表的中间结点
     * https://leetcode.cn/problems/middle-of-the-linked-list/description/
     */
    public ListNode middleNode(ListNode head) {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        ListNode solw = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            solw = solw.next;
            fast = fast.next.next;
        }
        return solw;
    }

    /**
     * 234回文链表
     * https://leetcode.cn/problems/palindrome-linked-list/description/
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }
        //找到中间对称位置，前面不变，后面翻转链表，在从前往后，从后往前判断是否相等
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //如果是奇数，则slow要往后走一步
        if(fast != null) {
            slow = slow.next;
        }
        //slow即为中间位置，翻转slow到fast节点的链表
        slow = reserse(slow);
        //翻转完了，前往后，后往前
        fast = head;
        while(slow != null) {
            if(fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
    //翻转链表
    public ListNode reserse(ListNode head) {
        ListNode prev = null;
        while(head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    /**
     * 206翻转链表
     * https://leetcode.cn/problems/reverse-linked-list/
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        ListNode listHead = head;
        ListNode cur = listHead.next;
        listHead.next = null;

        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = listHead;
            listHead = cur;
            cur = curNext;
        }
        return listHead;
    }
}